#include <cstdint>
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;
using ll = int64_t;
static inline constexpr ll MOD = 1e9+7;

static inline constexpr ll fpow(ll b, ll e, ll mod) {
    ll res = 1;
    b %= mod;
    while (e) {
        if (e & 1) 
            res = (res * b) % mod;
        b = (b * b) % mod;
        e >>= 1;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        string s;
        ll p;
        cin >> s >> p;
        int n = s.size();
        if (n == 0) {
            cout << "1\n";
            continue;
        }

        vector<ll> p10(n+1);
        p10[0] = 1;
        for (int i = 1; i <= n; i++) {
            p10[i] = (p10[i-1] * 10) % p;
        }

        ll inv10b = fpow(10, p-2, p);

        vector<ll> inv10(n+1);
        inv10[0] = 1;
        for (int i = 1; i <= n; i++) {
            inv10[i] = (inv10[i-1] * inv10b) % p;
        }

        vector<ll> pre(n+1, 0);
        for (int i = 1; i <= n; i++) {
            pre[i] = (pre[i-1] * 10 + (s[i-1] - '0')) % p;
        }

        vector<ll> val(n+1);
        for (int i = 0; i <= n; i++) {
            val[i] = pre[i] * inv10[i] % p; //
            if (val[i] < 0) val[i] += p;
        }

        unordered_map<ll, pair<ll, ll>> dic;
        ll tot1 = 1;
        dic[val[0]] = make_pair(1, 1);

        ll ndp0 = 0, ndp1 = 0;
        for (int i = 1; i <= n; i++) {
            ll v = val[i];
            ll s01 = 0, s1 = 0;
            auto it = dic.find(v);
            if (it != dic.end()) {
                s01 = it->second.first;
                s1 = it->second.second;
            }

            ndp1 = s01 % MOD;
            ndp0 = (tot1 - s1) % MOD;
            if (ndp0 < 0) 
                ndp0 += MOD;

            tot1 = (tot1 + ndp1) % MOD;

            ll add01 = (ndp0 + ndp1) % MOD;
            ll add1 = ndp1 % MOD;
            if (dic.find(v) != dic.end()) {
                dic[v].first = (dic[v].first + add01) % MOD;
                dic[v].second = (dic[v].second + add1) % MOD;
            } else {
                dic[v] = make_pair(add01, add1);
            }
        }

        ll ans = (ndp0 + ndp1) % MOD;
        cout << ans << '\n';
    }
    return 0;
}